#include<stdlib.h>
#include<string.h>
#include"seqlist.h"

static int isfull(const seqlist *mylist);

int seqlist_init(seqlist **mylist, int size, int cap){
	*mylist = malloc(sizeof(seqlist));
	if(NULL == *mylist){
		return -1;
	}
	(*mylist)->arr = calloc(cap, size);
	if(NULL == (*mylist)->arr){
		free(*mylist);
		*mylist = NULL;
		(*mylist)->arr = NULL;
		return -1;
	}
	(*mylist)->nnum = 0;
	(*mylist)->size = size;
	(*mylist)->cap = cap;

	return 0;

}

static int isfull(const seqlist *mylist){
	return mylist->nnum == mylist->cap;
}

int seqlist_insert(seqlist *mylist, const void *data){
	if(isfull(mylist)){
		return -1;
	}
	memcpy((char *)(mylist->arr) + mylist->nnum * mylist->size, data, mylist->size);
	mylist->nnum += 1;
	return 0;
}

int __find(const seqlist *mylist, const void *data,cmp cmp_t){
	int i;
	for(i = 0; i < mylist->nnum; i++){
		if(!cmp_t((char *)mylist->arr + i * mylist->size,data)){
			return i;
		}
	}
	return -1;
}

void *seqlist_find(const seqlist *mylist, const void *data,cmp cmp_t){
	int index = __find(mylist, data, cmp_t);
	if(index == -1){
		return NULL;
	}
	return (char *)mylist->arr + index * mylist->size;		
}
int seqlist_delete(seqlist *mylist, const void *data, cmp cmp_t){
	int index = __find(mylist, data, cmp_t);
	if(index == -1){
		return -1;
	}
	memmove((char *)mylist->arr + index * mylist->size, (char *)mylist->arr + (index + 1) * mylist->size, (mylist->nnum - (index + 1)) * mylist->size);
	mylist->nnum -= 1;
	return 0;
}

int seqlist_update(const seqlist *mylist, const void *data1, const void *data2,cmp cmp_t){
	int index =  __find(mylist, data1, cmp_t);
	if(index == -1){
		return -1;
	}
	memcpy((char *)mylist->arr + index * mylist->size, data2, mylist->size);
	return 0;
}

void seqlist_show(const seqlist *mylist, pri pri_t){
	for(int i = 0; i < mylist->nnum; i++){
		pri_t((char *)mylist->arr  + i * mylist->size);
	}
}


void seqlist_destriy(seqlist **mylist){
	if (*mylist == NULL)
		return;

	free((*mylist)->arr);
	(*mylist)->arr = NULL;
	free(*mylist);
	*mylist = NULL;
}





void my_qsort(seqlist *mylist, int left, int right, cmp cmp_t){
	int i = left;
	int j = right;
	int index;
	char * p = (char *)mylist->arr;
	void *pivot = malloc(mylist->size);
	memcpy(pivot, p + i * mylist->size , mylist->size);
	if(i < j){
		while(i < j){
			while(i < j && cmp_t(p + j * mylist->size, pivot) >= 0){
				j--;
			}
			memcpy(p + i * mylist->size, p + j * mylist ->size, mylist->size);

			while(i < j && cmp_t(p + i * mylist->size, pivot) <= 0){
				i++;
			}
			memcpy(p + j * mylist->size, p + i * mylist ->size, mylist->size);
		}
		memcpy(p + i * mylist->size, pivot, mylist->size);
		free(pivot);
		pivot = NULL;
		index = i;
		my_qsort(mylist, left, index -1, cmp_t);
		my_qsort(mylist, index + 1, right, cmp_t);
	}
	return;
}

static void __swap(void *data1, void *data2, int size)
{
	void *t = malloc(size);

	memcpy(t, data1, size);
	memcpy(data1, data2, size);
	memcpy(data2, t, size);

	free(t);
	t = NULL;
}

void seqlist_reverse(seqlist_t *mylist)
{
    int i, j;

    for (i = 0, j = mylist->nmemb - 1; i < j; i++, j--)
        __swap((char *)mylist->arr + i * mylist->size, (char *)mylist->arr + j * mylist->size, mylist->size);
}


static int __bsearch(const void *arr, int left, int right, int size, cmp cmp_t, const void *key){
    int mid;
    int res;

    if (left > right)
        return -1;

    mid = (left + right) / 2;
    res = cmp_t((char *)arr + mid * size, key);

    if (res == 0)
        return mid;
    else if (res > 0)
        return __bsearch(arr, left, mid - 1, size, cmp_t, key);
    else
        return __bsearch(arr, mid + 1, right, size, cmp_t, key);
}

void *seqlist_bsearch(seqlist * mylist, cmp cmp_t, const void *key){
    int f;
	const void * arr = mylist->arr;
	int nmemb = mylist->nnum;
	int size = mylist->size;

    f = __bsearch(arr, 0, nmemb - 1, size, cmp_t, key);

    if (f == -1)
        return NULL;

    return (char *)arr + f * size;
}


int seqlist_reverse_new(const seqlist_t *mylist, seqlist_t **dest)
{
	int i;
	void *ele;

	if (mylist == NULL || *dest == NULL)
		return -1;

	if (seqlist_init(dest, mylist->size, mylist->capacity) != 0)
		return -1;

	for (i = mylist->nmemb - 1; i >= 0; i--) {
		ele = (char *)mylist->arr + i * mylist->size;
		if (seqlist_insert(*dest, ele) == -1) {
			seqlist_destroy(dest);
			return -1;
		}
	}

	return 0;
}

